package algorithm.array;

import java.util.Arrays;

/**
 * leetcode : https://leetcode.com/problems/move-zeroes/description/
 * Difficulty : Easy
 *
 * 给一个数组，把其中的0都移动到数组末尾，并且其中非0数字的顺序不能改变
 * @Author Antony
 * @Since 2018/7/20 15:20
 */
public class MoveZeros {


    public static void main(String[] args) {
        int[] arr = new int[]{1,0,0,3,0,4,0,5,6,8,0};
        moveZeroes(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * beats 100.0% - 1ms
     * 思路：
     * 先找到0点记为ZeroIndex
     * 从zeroIndex+1 往后找找到不是0点的索引i
     * nums[zeroIndex] 和 nums[i] 交换，同时zeroIndex++
     * 一直到i到头
     */
    public static void moveZeroes(int[] nums) {
        int zeroPoint = -1;
        for(int i=0; i<nums.length; i++){
            if(nums[i] == 0) {
                zeroPoint = i;
                break;
            }
        }
        if(zeroPoint == -1) return;
        for(int j=zeroPoint+1; j<nums.length; j++){
            if(nums[j] != 0){
                nums[zeroPoint++] = nums[j];
                nums[j] = 0;
            }
        }
    }
}
